//
// Created by Win10 on 2023/4/8.
//

#ifndef C_DATA_STRUCTURE_BUCKET_SORT_H
#define C_DATA_STRUCTURE_BUCKET_SORT_H


#include <algorithm>
#include <vector>

template<typename T>
//整数或浮点数皆可使用
void bucket_sort(T a[], int len, int noOfBuckets) {
  using namespace std;
  T max_ele = a[0];
  T min_ele = a[0];
  for(int i=0;i<len;i++){
    if(a[i]>max_ele)max_ele=a[i];
    if(a[i]<min_ele)min_ele=a[i];
  }

  // range (for buckets)
  double rnge = (max_ele - min_ele) / (double )noOfBuckets;

  vector<vector<T>> temp;

  // create empty buckets
  for (int i = 0; i < noOfBuckets; i++) {
    temp.push_back(vector<T>());
  }

  // scatter the array elements into the correct bucket
  for (int i = 0; i < len; i++) {
    double diff = (a[i] - min_ele) / rnge
                  - int((a[i] - min_ele) / rnge);

    // append the boundary elements to the lower array
    if (diff == 0 && a[i] != min_ele) {
      temp[int((a[i] - min_ele) / rnge) - 1]
              .push_back(a[i]);
    }
    else {
      temp[int((a[i] - min_ele) / rnge)].push_back(
              a[i]);
    }
  }

  // Sort each bucket individually
  for (int i = 0; i < temp.size(); i++) {
    if (!temp[i].empty()) {
      sort(temp[i].begin(), temp[i].end());
    }
  }

  // Gather sorted elements to the original array
  int k = 0;
  for (vector<T>& lst : temp) {
    if (!lst.empty()) {
      for (T i : lst) {
        a[k] = i;
        k++;
      }
    }
  }
}

#endif //C_DATA_STRUCTURE_BUCKET_SORT_H
